package dictTrie;

public class Trie {

    Node head;

    /** Initialize your data structure here. */
    public Trie() {
        head = new Node();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        int i = 0;
        Node[] ptr = head.nodes;
        Node pre = head;
        while (i < word.length() && ptr[word.charAt(i) - 'a'] != null){
            pre = ptr[word.charAt(i) - 'a'];
            ptr =ptr[word.charAt(i) - 'a'].nodes;
            i++;
        }
        if (i == word.length()){
            pre.isLeaf = true;
            return;
        }
        Node node = null;
        for (int j = i; j < word.length(); j++){
            node = new Node(word.charAt(i), false);
            ptr[word.charAt(j) - 'a'] = node;
            ptr = node.nodes;
        }
        if (node != null){
            node.isLeaf = true;
        }
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        int i = 0;
        Node[] ptr = head.nodes;
        Node pre = head;
        while (i < word.length() &&ptr[word.charAt(i) - 'a'] != null){
            pre = ptr[word.charAt(i) - 'a'];
            ptr =ptr[word.charAt(i) - 'a'].nodes;

            i++;
        }
        if (i == word.length() && pre.isLeaf){
            return true;
        } else {
            return false;
        }
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        int i = 0;
        Node[] ptr = head.nodes;
        while (i < prefix.length() &&ptr[prefix.charAt(i) - 'a'] != null){
            ptr =ptr[prefix.charAt(i) - 'a'].nodes;
            i++;
        }
        if (i == prefix.length()){
            return true;
        } else {
            return false;
        }
    }
}
class Node{
    char c;
    boolean isLeaf;
    Node[] nodes = new Node[26];

    Node(){

    }

    Node(char c, boolean isLeaf){
        this.c = c;
        this.isLeaf = isLeaf;
    }
}